package xkp.lesson5;

import org.junit.Test;

public class JunitTest {
	String str = "";
	//此时arr的生存范围为整个类中
	int[] arr = {2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124,
			2,4,6,21,567,12,543,321,
			432,654,6,1234,345,5,23,
			54,876,23,4,645,123,23,
			345,435,534,534,235,432,42,43234,
			23655,4756,3244,345,457,2334,
			756,234,346,234,54667,456234,7876,
			21414,68567445,12312,45645,86474,2352,57465,
			234324,574674,324234,6785685,44,66,88,213123,
			545,2,34542,213,213,2133,21,432,54,32,
			543,5,43,6,43,653,6,54376,
			547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
			213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
			1058,24589,1248,123,876,1224,9068,134,67547,124
	};


	@Test
	public void testMaoPao() {
		//13ms  6ms  12s
		//322  276
		//for(int i = 1; i <= 100; i++) {
		maopao(arr);
		//}
	}


	@Test
	public void testquickSort() {
		//485 619
		//for(int i = 1; i <= 100; i++) {
		quickSort(arr, 0, arr.length-1);
		//}
	}

	@Test
	public void testSearch() {
		for(int i = 1; i <= 10000; i++) {
			//searchKey(arr, 100);
			binarySearch(arr, 100);
		}
	}

	//冒泡
	/**
	 * 冒泡排序
	 * @param arr  需要被排序的数组
	 */
	public int[] maopao(int[] arr) {
		//i是冒泡的个数
		for(int i = 0; i< arr.length-1; i++) {
			//每个泡要向上冒几次
			//arr.length-1是为了避免arr[j+1]越界
			//减i是为了提高效率，避免不需要的操作
			for(int j = 0; j < arr.length-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					//此处直接操作原数组进行交换
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
		//冒泡排序后的结果需不需要返回
		//
	}
	//快速
	public void quickSort(int[] arr,int low,int high){
		int i,j,temp,t;
		if(low>=high){
			return;
		}
		i=low;
		j=high;
		//temp就是基准位
		temp = arr[low];

		while (i<j) {
			//先看右边，依次往左递减
			while (temp<=arr[j]&&i<j) {
				j--;
			}
			//再看左边，依次往右递增
			while (temp>=arr[i]&&i<j) {
				i++;
			}
			//如果满足条件则交换
			if (i<j) {
				t = arr[j];
				arr[j] = arr[i];
				arr[i] = t;
			}

		}
		//最后将基准为与i和j相等位置的数字交换
		arr[low] = arr[i];
		arr[i] = temp;
		//递归调用左半数组
		quickSort(arr, low, j-1);
		//递归调用右半数组
		quickSort(arr, j+1, high);
	}



	//普通查找
	public int searchKey(int[] arr,int value) {
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == value) {
				return i;
			}
		}
		return -1;
	}

	//二分查找
	public int binarySearch(int[] arr,int key) {
		//定义三个索引位置。
		int min = 0;
		int max = arr.length - 1;
		int mid = 0;
		//循环折半，条件， min<=max
		while(min <= max) {
			//公式，计算中间索引
			mid = (min+max)/2;
			//让被找元素和中间索引元素进行比较
			if(key>arr[mid]) {
				min = mid +1;
			}else if(key <arr[mid]) {
				max = mid -1;
			}else {
				//找到元素，返回元素索引
				return mid;
			}
		}
		return -1;
	}

}
